# !/usr/bin/env python	1	
# coding:utf-8		
# Author:   < group 30 >		
# Purpose:		
# Created: 14/10/2012

import getopt, sys, copy, time, argparse, textwrap
from search import *
from operator import attrgetter

def heuristic(node):
    if _nbreVisitedNode: 
        global _visitedNode
        _visitedNode += 1
        if _debug: print("Numbre of visited Nodes :", self.visitedNode)
    return manhattan_boxes(node) + manhattan_avatar(node)

def manhattan_avatar(node):
    boxes = node.state.boxes[:]
    avatar = node.state.avatar
    distance = len(node.state.board.board) + len(node.state.board.board[0])
    
    for box in boxes:
        current = manhattan_distance(box, avatar)
        if current < distance: distance = current
    return distance

def manhattan_boxes(node):
    targets = node.state.board.targets
    boxes = node.state.boxes[:]
    max_distance = len(node.state.board.board) + len(node.state.board.board[0])
    distance = 0

    for target in targets:
        current = max_distance
        index = -1
        for i, box in enumerate(boxes):
            dist = manhattan_distance(target, box)
            if dist < current:
                current = dist
                index = i
        if index == -1:
            raise Exception("Error : distance between target and boxes are higher than board hight + width") 
        distance += current
        boxes.pop(index)
    return distance

def manhattan_distance(self, other):
    return abs(self.i - other.i) + abs(self.j - other.j)

class IllegalCallError(Exception):
    pass

class FileFomartError(Exception):
    pass

class SokobanProblem(Problem):
    def __init__(self, sokoban_init, sokoban_goal):
        self.board, self.initial = self.parse_file(sokoban_init, sokoban_goal)

    def successor(self, state):
        board = state.board

        for direction in ["up", "down", "left", "right"]:

            if _debug:
                print(state)
                print('\t\tinspect : %i, %i \n' % (inspected_position[0], inspected_position[1]))
                print(board)
                if _step : input("-------------------------------- press any key to continue ----------------------------------------")
            
            inspected_position = state.avatar.get_position(direction)        
            if board.is_free(inspected_position):
                new_board = board.__copy__()
                new_board.board[inspected_position[0]][inspected_position[1]] = '@'
                new_board.board[state.avatar.i][state.avatar.j] = ' ' 
                
                yield direction, SokobanState(state.boxes, Position(inspected_position), new_board )
            elif board.is_boxe(inspected_position):
                box = state.get_box_at_position(inspected_position) 
                box_possible_position = box.get_position(direction)
                if board.is_free(box_possible_position) and not board.is_blocked(box, box_possible_position):
                    new_board = board.__copy__()
                    new_board.board[inspected_position[0]][inspected_position[1]] = '@'
                    new_board.board[state.avatar.i][state.avatar.j] = ' ' 
                    new_boxes = state.boxes[:]
                    for i,b in enumerate(new_boxes):
                        if b == box : 
                            new_boxes[i] = copy.copy(box)
                            new_boxes[i].move(direction)
                            new_board.board[new_boxes[i].i][new_boxes[i].j] = '$'
                    
                    new_boxes.sort(key=attrgetter('i', 'j'))
                    new_board.targets.sort(key=attrgetter('i', 'j'))
                    yield direction, SokobanState(new_boxes, Position(inspected_position), new_board )

    def goal_test(self, state):
        for boxe in state.boxes:
            if boxe not in state.board.targets:
                return False
        return True

    def parse_file(self, sokoban_init, sokoban_goal):
        
        boxes = []
        targets = []
        avatar = Position([-1, -1])

        def parse_element(i, j, char):
            if char == " ":
                return char 
            elif char == "$":
                boxes.append(Position([i, j]))
                return char
            elif char == "@":
                avatar.i, avatar.j = i,j
                return char
            elif char == ".":
                targets.append(Position([i, j]))
                if _debug : matrix[i][j] = char
            elif char == "#":
                return char
            else:    
                raise FileFormatError("File fomat error : Character non reconized")

        def parse_line(i, line):
            return [parse_element(i, j, char) for j, char in enumerate(line)]
        try:
            fd = open(sokoban_init, 'r')
            matrix = [parse_line(i, line) for i, line in enumerate(fd.read().splitlines(False))]
            fd.close()
            fd = open(sokoban_goal, 'r')
            [parse_line(i, line) for i, line in enumerate(fd.read().splitlines(False))]
            fd.close()
        except:
            print("A problem has occured using files, check path to goal and init")
            sys.exit(-1)

        if avatar.i == -1 or avatar.j == -1:
            raise FileFormatError("File Format Error : no avatar found")
        
        if len(targets) != len(boxes):
            raise FileFormatError

        board = Board(matrix, targets)
        state = SokobanState(boxes, avatar, board)

        return board, state

class SokobanState():
    def __init__(self, boxes, avatar, board):
        self.boxes, self.avatar, self.board = boxes, avatar, board

    def __eq__(self, other):
        for box in self.boxes :
            if box not in other.boxes :
                return False
        if self.avatar != other.avatar :
            return False
        return True

    def __hash__(self):
        return (str(self.avatar.i)+str(self.avatar.j) + "".join(["%d%d" % (pos.i, pos.j) for pos in self.boxes])).__hash__()

    def __str__(self):
        if _debug:
            boxString = ""
            for box in self.boxes :
                    boxString += "\t" + str(box) + "\n"
            return "[-------State-------\n Boxes : \n" + str(boxString) + "\n" + " Avatar : " + str(self.avatar) + "\n--------------------]\n"
        else: 
            return str(self.board)
    
    def get_box_at_position(self, position):
        for box in self.boxes:
            if box.i == position[0] and box.j == position[1]:
                return box
        raise Exception("box not found in : (%i, %i)" % (position[0], position[1]))
    
class Board():
    def __init__(self, board, targets, blocked_positions = None):
        self.board, self.targets = board, targets
        #if blocked_positions is None : 
        #    self.blocked_positions = self.init_blocked_positions()
        #else:
        self.blocked_positions = blocked_positions
    
    def is_boxe(self, pos):
        if _debug:
            print("Searching for box at :", pos)
        i, j = pos[0], pos[1]
        if self.board[i][j] == '$':
            if _debug : print("Box found at :", pos)
            return True
        if _debug: print("Box not found at :", pos)
        return False

    def is_target(self, pos):
        x, y = pos[0], pos[1]
        if self.board[y][x] == '.':
            return True
        else : return False

    def is_blocked(self, box, new_position):
        i, j = new_position[0], new_position[1] # du boxe possible position
        if _debug:
            print("is_blocked : ", end = ' ')
            print(position)
        
        pos = Position([i, j])
        #if self.blocked_positions is None:
        #    self.blocked_positions = self.init_blocked_positions(box, pos)
        if pos is self.is_blocked_position(box,pos):
            if _debug:
                print("position is a blocked one")
                if _step : input("press any key to continue")
            
            return True
        else: return False

    def is_free(self, pos):
        i, j = pos[0], pos[1]
        if self.board[i][j] == ' ' or self.board[i][j] == '.':
            if _debug:
                print("\n-----> was free : ", pos, '\n')
            return True
        if _debug:
            print("\n-----> wasn't free : ", pos, '\n')
        return False
    
    def is_blocked_position(self, box, pos):
        # It finds the dead positions, ex: against a wall without target on the line
        blocked_pos =[]
        #-- where $ is stuck in corner between 2 # or $
        for i in range(-1,2):
            for j in range(-1,2):
                if (abs(i)+abs(j)) % 2 !=0:
                    if self.is_free([pos.i+i,pos.j+j]) is False:
                        blocked_pos.append(Position([pos.i+i,pos.j+j]))
        blocked_pos.remove(box)
        if len(blocked_pos)>2 : return True
        elif len(blocked_pos)==2:
            if abs(blocked_pos[0].i-blocked_pos[1].i)==1 and abs(blocked_pos[0].j-blocked_pos[1].j)==1 :
                return True
        
        
        # -- where the position is agaisnt a wall 
        next_step = [ pos.i-box.i, pos.j-box.j]  # [-1,0] or [0,1] or ...
        if self.is_free(next_step): return False 
        elif self.is_wall([pos.i,pos.j],next_step):  
            if abs(next_step[0])==1: # horizontal wall
                return self.limited_to_left(pos, next_step) and self.limited_to_right(pos, next_step)
            if abs(next_step[1])==1: # vertical wall
                return self.limited_to_top(pos, next_step) and self.limited_to_bottom(pos, next_step)
        
        return False
    
    def is_wall(self, pos, next_step):
        return self.board[pos[0]+next_step[0]][pos[1]+next_step[1]] == "#"
    
    def limited_to_left(self,pos, next_step):
        for j in range(1 , pos.j+1):
            symbol_on_board = self.board[pos.i][pos.j-j]
            if self.is_wall([pos.i,pos.j-j],next_step): 
                if symbol_on_board == '.' : # a tagrget on the line
                    return False
                if symbol_on_board == '$' or symbol_on_board == "#":
                    return True
            else: 
                return False
        return None
    
    def limited_to_right(self, pos, next_step):
        for j in range(1 , len(self.board[pos.i+next_step[0]])):
            symbol_on_board = self.board[pos.i][pos.j+j] 
            if self.is_wall([pos.i,pos.j+j],next_step): 
                if symbol_on_board == '.' : # a tagrget on the column
                    return False
                if symbol_on_board == '$' or symbol_on_board == "#":
                    return True
            else: 
                return False 
        return None

    def limited_to_top(self, pos, next_step):
        for i in range( 1, pos.i+1):
            if self.is_wall([pos.i-i,pos.j],next_step): 
                symbol_on_board = self.board[pos.i-i][pos.j ]
                if symbol_on_board == '.' : # a tagrget on the line
                    return False
                if symbol_on_board == '$' or symbol_on_board == "#":
                    return True
            else: 
                return False
        return None
    
    def limited_to_bottom(self, pos, next_step):
        for i in range(1 , len(self.board)):
            if self.is_wall([pos.i+i,pos.j],next_step): 
                symbol_on_board = self.board[pos.i+i][pos.j ] 
                if symbol_on_board == '.' : # a tagrget on the column
                    return False
                if symbol_on_board == '$' or symbol_on_board == "#":
                    return True
            else: 
                return False
        return None
    
    def against_vertical_wall(self,pos):
        return pos.j==1 or pos.j == len(self.board[pos.i])-2
    
    def against_horizontal_wall(self,pos):
        return pos.i==1 or pos.i == len(self.board)-2 
    
    def __str__(self):
        
        boardString = ""
        if _debug :
            targetString = ""
            for target in self.targets :
                targetString += "\t" + str(target) + "\n"
            
            for line in self.board :
                boardString += "\t"
                for e in line :
                    boardString += " " + str(e)
                boardString += "\n"
            
            return "[-------Board-------\n Targets : \n" + str(targetString) +\
                   "\n" + " Board :\n\n" + boardString  + "\n---------------]\n"
        else:
            for line in self.board :
                for e in line :
                    boardString += str(e)
                boardString += "\n"       
            return boardString
        
    def print_board():
        for i in self.board:
            for j in i:
                print(j, end=' ')
            print()

    def __copy__(self):
        board = [[ny for ny in nx] for nx in self.board]
        
        return Board(board, self.targets[:], self.blocked_positions)

    def __deepcopy__(self):
        return self.__copy__()

class Position():
    def __init__(self, pos):
        self.i, self.j = pos[0], pos[1]
        
    def __eq__(self, other):
        return self.i == other.i and self.j == other.j
                
    def get_position(self, direction):
        position = {'up' : [self.i - 1, self.j],
                'down' : [self.i + 1, self.j],
                'left' : [self.i, self.j - 1],
                'right' : [self.i, self.j + 1] }
        return position[direction]
    
    def move(self, direction) :
        move = {'up' : [-1, 0],
                'down' : [1, 0],
                'left' : [0, -1],
                'right' : [0, 1] }
        self.do_move(move[direction])
    
    def do_move(self, move) :
        self.i += move[0]
        self.j += move[1]
    
    # return the minimal Position (needed for .sort() )
    def __lt__(self, other):
        if self.i < other.i :
            return self
        elif self.i == other.i and self.j < other.j :
            return self
        else : # self.i > other.i
            return other

    def __str__(self):
        return str([self.i, self.j])
    
    def __copy__(self):
        return Position([self.i, self.j])
    
#def usage():
#    print('----->\ttry : python3 main.py $(pwd)/benchs/sokoInst01.init $(pwd)/benchs/sokoInst01.goal')

def main():
    global _debug, _step, _nbreVisitedNode, _timer, _start_time
    global _visitedNode

    parser = argparse.ArgumentParser(
        formatter_class=argparse.RawDescriptionHelpFormatter,
        description=textwrap.dedent('''\
        Assignment 2 : LINGI2261 - Artificial Intelligence
        ---------------------------------------------------
        Informed search assignment
        '''), 
        epilog="---- Made by group 30 ----")
    parser.add_argument("init_file", action="store" , help="The init file")
    parser.add_argument("goal_file", action="store" , help="The goal file")    
    parser.add_argument("-d", "--debug", action="store_true", help="See the debugging mode on stdout")
    parser.add_argument("-t", "--time", action="store_true", help="Show on output running time")
    parser.add_argument("-p", "--perform", action="store_true", help="Show on output the number of explored nodes")
    parser.add_argument("-s", "--step", action="store_true", help = "Enable step by step execution, need debug mode")
    args = parser.parse_args( ) 
    
    sokoban_init, sokoban_goal, _debug = args.init_file, args.goal_file, args.debug
    _timer, _nbreVisitedNode =  args.time, args.perform
    _step = None
    
    if _timer : _start_time = time.time()
    if _debug:  _step = args.step
    if _nbreVisitedNode: _visitedNode = 0
    
    problem = SokobanProblem(sokoban_init, sokoban_goal)
    node = astar_graph_search(problem, heuristic)
    path = node.path()
    path.reverse()
    
    for n in path:
        print(n.state)
    
    if _timer: print("Time elapsed (sec):", time.time() - _start_time)
    if _nbreVisitedNode: 
        print("Numbre of visited Nodes :", _visitedNode)
        print("Numbre of move to solve :", len(path)-1) # -1 is initial position
        
    
if __name__ == "__main__":
    main()
